package com.leetcode.algs4.graph;

import com.leetcode.algs4.graph.least_path.EdgeWeightedDigraph;
import com.leetcode.algs4.graph.least_path.EdgeWeightedDirectedCycle;

/**
 * @author Dennis Li
 * @date 2020/6/16 16:05
 */
public class Topological {

    // 顶点的拓扑排序
    private  Iterable<Integer> order;

    public Topological(Digraph G){
        DirectedCycle cycleDetector = new DirectedCycle(G);
        if(!cycleDetector.hasCycle()){
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }

    public Topological(EdgeWeightedDigraph G) {
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }

    public Iterable<Integer> order() {
        return order;
    }
    public boolean isDAG(){
        return order != null;
    }

}
